//和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。 
//
// 给你一个整数数组 nums ，请你在所有可能的 子序列 中找到最长的和谐子序列的长度。 
//
// 数组的 子序列 是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。 
//
// 
//
// 示例 1： 
//
// 
// 输入：nums = [1,3,2,2,5,2,3,7] 
// 
//
// 输出：5 
//
// 解释： 
//
// 最长和谐子序列是 [3,2,2,2,3]。 
//
// 示例 2： 
//
// 
// 输入：nums = [1,2,3,4] 
// 
//
// 输出：2 
//
// 解释： 
//
// 最长和谐子序列是 [1,2]，[2,3] 和 [3,4]，长度都为 2。 
//
// 示例 3： 
//
// 
// 输入：nums = [1,1,1,1] 
// 
//
// 输出：0 
//
// 解释： 
//
// 不存在和谐子序列。 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 2 * 10⁴ 
// -10⁹ <= nums[i] <= 10⁹ 
// 
//
// Related Topics 数组 哈希表 计数 排序 滑动窗口 👍 426 👎 0


package LeetCode.editor.cn;


import java.util.Arrays;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * @author ldltd
 * @date 2025-06-30 09:28:16
 * @description 594.最长和谐子序列
 
 */
 
public class LongestHarmoniousSubsequence {
    public static void main(String[] args) {
    //测试代码
    LongestHarmoniousSubsequence fun = new LongestHarmoniousSubsequence();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        // 最大和最小差值是1，是不是说明其实只有两种数，a和b
    // 统计词频 稍微有点慢
    public int findLHS1(int[] nums) {
        int res=0;
        Map<Integer, Long> collect = Arrays.stream(nums).boxed().collect(Collectors.groupingBy(Integer::valueOf, Collectors.counting()));
        for (Map.Entry<Integer, Long> integerLongEntry : collect.entrySet()) {
            int key = integerLongEntry.getKey();
            // 如果key+1存在
            if (collect.containsKey(key + 1)) {
                // 计算和谐子序列长度
                long count = integerLongEntry.getValue() + collect.get(key + 1);
                // 更新最大长度
                if (count > res) {
                   res= (int) count;
                }
            }
        }
        return res;
    }
    // 排序后统计临近的
    public int findLHS(int[] nums) {
        Arrays.sort(nums);
        int begin = 0;
        int res = 0;
        for (int end = 0; end < nums.length; end++) {
            //跳过差值大于1的部分，因为是递增排序的
            while (nums[end] - nums[begin] > 1) {
                begin++;
            }
            // 如果差值正好是1，更新最大长度
            if (nums[end] - nums[begin] == 1) {
                res = Math.max(res, end - begin + 1);
            }
        }
        return res;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
